{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Orders in the Backlog"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #simulation #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #模拟 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getNumberOfBacklogOrders"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #积压订单中的订单总数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二维整数数组 <code>orders</code> ，其中每个 <code>orders[i] = [price<sub>i</sub>, amount<sub>i</sub>, orderType<sub>i</sub>]</code> 表示有 <code>amount<sub>i</sub></code><sub> </sub>笔类型为 <code>orderType<sub>i</sub></code> 、价格为 <code>price<sub>i</sub></code> 的订单。</p>\n",
    "\n",
    "<p>订单类型 <code>orderType<sub>i</sub></code> 可以分为两种：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0</code> 表示这是一批采购订单 <code>buy</code></li>\n",
    "\t<li><code>1</code> 表示这是一批销售订单 <code>sell</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>注意，<code>orders[i]</code> 表示一批共计 <code>amount<sub>i</sub></code> 笔的独立订单，这些订单的价格和类型相同。对于所有有效的 <code>i</code> ，由 <code>orders[i]</code> 表示的所有订单提交时间均早于 <code>orders[i+1]</code> 表示的所有订单。</p>\n",
    "\n",
    "<p>存在由未执行订单组成的 <strong>积压订单</strong> 。积压订单最初是空的。提交订单时，会发生以下情况：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果该订单是一笔采购订单 <code>buy</code> ，则可以查看积压订单中价格 <strong>最低</strong> 的销售订单 <code>sell</code> 。如果该销售订单 <code>sell</code> 的价格 <strong>低于或等于</strong> 当前采购订单 <code>buy</code> 的价格，则匹配并执行这两笔订单，并将销售订单 <code>sell</code> 从积压订单中删除。否则，采购订单 <code>buy</code> 将会添加到积压订单中。</li>\n",
    "\t<li>反之亦然，如果该订单是一笔销售订单 <code>sell</code> ，则可以查看积压订单中价格 <strong>最高</strong> 的采购订单 <code>buy</code> 。如果该采购订单 <code>buy</code> 的价格 <strong>高于或等于</strong> 当前销售订单 <code>sell</code> 的价格，则匹配并执行这两笔订单，并将采购订单 <code>buy</code> 从积压订单中删除。否则，销售订单 <code>sell</code> 将会添加到积压订单中。</li>\n",
    "</ul>\n",
    "\n",
    "<p>输入所有订单后，返回积压订单中的 <strong>订单总数</strong> 。由于数字可能很大，所以需要返回对 <code>10<sup>9</sup> + 7</code> 取余的结果。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/03/21/ex1.png\" style=\"width: 450px; height: 479px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>orders = [[10,5,0],[15,2,1],[25,1,1],[30,4,0]]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>输入订单后会发生下述情况：\n",
    "- 提交 5 笔采购订单，价格为 10 。没有销售订单，所以这 5 笔订单添加到积压订单中。\n",
    "- 提交 2 笔销售订单，价格为 15 。没有采购订单的价格大于或等于 15 ，所以这 2 笔订单添加到积压订单中。\n",
    "- 提交 1 笔销售订单，价格为 25 。没有采购订单的价格大于或等于 25 ，所以这 1 笔订单添加到积压订单中。\n",
    "- 提交 4 笔采购订单，价格为 30 。前 2 笔采购订单与价格最低（价格为 15）的 2 笔销售订单匹配，从积压订单中删除这 2 笔销售订单。第 3 笔采购订单与价格最低的 1 笔销售订单匹配，销售订单价格为 25 ，从积压订单中删除这 1 笔销售订单。积压订单中不存在更多销售订单，所以第 4 笔采购订单需要添加到积压订单中。\n",
    "最终，积压订单中有 5 笔价格为 10 的采购订单，和 1 笔价格为 30 的采购订单。所以积压订单中的订单总数为 6 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/03/21/ex2.png\" style=\"width: 450px; height: 584px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>orders = [[7,1000000000,1],[15,3,0],[5,999999995,0],[5,1,1]]\n",
    "<strong>输出：</strong>999999984\n",
    "<strong>解释：</strong>输入订单后会发生下述情况：\n",
    "- 提交 10<sup>9</sup> 笔销售订单，价格为 7 。没有采购订单，所以这 10<sup>9</sup> 笔订单添加到积压订单中。\n",
    "- 提交 3 笔采购订单，价格为 15 。这些采购订单与价格最低（价格为 7 ）的 3 笔销售订单匹配，从积压订单中删除这 3 笔销售订单。\n",
    "- 提交 999999995 笔采购订单，价格为 5 。销售订单的最低价为 7 ，所以这 999999995 笔订单添加到积压订单中。\n",
    "- 提交 1 笔销售订单，价格为 5 。这笔销售订单与价格最高（价格为 5 ）的 1 笔采购订单匹配，从积压订单中删除这 1 笔采购订单。\n",
    "最终，积压订单中有 (1000000000-3) 笔价格为 7 的销售订单，和 (999999995-1) 笔价格为 5 的采购订单。所以积压订单中的订单总数为 1999999991 ，等于 999999984 % (10<sup>9</sup> + 7) 。</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= orders.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>orders[i].length == 3</code></li>\n",
    "\t<li><code>1 <= price<sub>i</sub>, amount<sub>i</sub> <= 10<sup>9</sup></code></li>\n",
    "\t<li><code>orderType<sub>i</sub></code> 为 <code>0</code> 或 <code>1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-orders-in-the-backlog](https://leetcode.cn/problems/number-of-orders-in-the-backlog/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-orders-in-the-backlog](https://leetcode.cn/problems/number-of-orders-in-the-backlog/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[10,5,0],[15,2,1],[25,1,1],[30,4,0]]', '[[7,1000000000,1],[15,3,0],[5,999999995,0],[5,1,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "\n",
    "    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:\n",
    "        class Order:\n",
    "            def __init__(self, price, amount):\n",
    "                self.mPrice = price\n",
    "                self.mAmount = amount\n",
    "            def output(self):\n",
    "                print(f\"Price:{self.mPrice} Amount:{self.mAmount}\")\n",
    "\n",
    "            def __eq__(self, other):\n",
    "                return self.mPrice == other.mPrice\n",
    "\n",
    "            def __lt__(self, other):\n",
    "                return self.mPrice < other.mPrice\n",
    "\n",
    "        buy_list = []\n",
    "        sell_list = []\n",
    "\n",
    "        for o in orders:\n",
    "            # for buy in buy_list:\n",
    "            #     buy.output()\n",
    "            # print(\"----------------------------\")\n",
    "            # for sell in sell_list:\n",
    "            #     sell.output()\n",
    "            # print(\"=============================\")\n",
    "            price = o[0]\n",
    "            amount = o[1]\n",
    "            orderType = o[2]\n",
    "            if orderType == 1:\n",
    "                while amount and len(buy_list) > 0 and -buy_list[0].mPrice >= price:\n",
    "                    if buy_list[0].mAmount > amount:\n",
    "                        buy_list[0].mAmount -= amount\n",
    "                        amount = 0\n",
    "                        break\n",
    "                    else:\n",
    "                        amount -= heappop(buy_list).mAmount\n",
    "                        # buy_list.pop(0)\n",
    "                if amount > 0:\n",
    "                    # 加入 sell_list\n",
    "                    sell_object = Order(price, amount)\n",
    "                    heappush(sell_list, sell_object)\n",
    "                    # tmp_list = []\n",
    "                    # sell_object = Order(price, amount)\n",
    "                    # length = len(sell_list)\n",
    "                    # if length>0:\n",
    "                    #     merged = False\n",
    "                    #     for i in range(length-1, -1, -1):\n",
    "                    #         if sell_list[i].mPrice > sell_object.mPrice:\n",
    "                    #             sell_list.append(sell_object)\n",
    "                    #             sell_list.extend(tmp_list)\n",
    "                    #             merged = True\n",
    "                    #             break\n",
    "                    #         elif sell_list[i].mPrice == sell_object.mPrice:\n",
    "                    #             sell_list[i].mAmount += sell_object.mAmount\n",
    "                    #             sell_list.extend(tmp_list)\n",
    "                    #             merged = True\n",
    "                    #             break\n",
    "                    #         else:\n",
    "                    #             tmp_list.insert(0,sell_list[i])\n",
    "                    #             sell_list.pop(i)\n",
    "                                \n",
    "                    #     if not merged:\n",
    "                    #         if sell_object.mAmount > 0:\n",
    "                    #             sell_list.append(sell_object)\n",
    "                    #         sell_list.extend(tmp_list)\n",
    "                    # else:\n",
    "                    #     sell_list.append(sell_object)\n",
    "                        \n",
    "            elif orderType == 0:\n",
    "                while amount and len(sell_list) > 0 and sell_list[0].mPrice <= price:\n",
    "                    if sell_list[0].mAmount > amount:\n",
    "                        sell_list[0].mAmount -= amount\n",
    "                        amount = 0\n",
    "                        break\n",
    "                    else:\n",
    "                        amount -= heappop(sell_list).mAmount\n",
    "                        # sell_list.pop(0)\n",
    "                if amount > 0:\n",
    "                    buy_object = Order(-price, amount)\n",
    "                    heappush(buy_list, buy_object)\n",
    "                    # # 加入 buy_list\n",
    "                    # tmp_list = []\n",
    "                    # buy_object = Order(price, amount)\n",
    "                    # length = len(buy_list)\n",
    "                    # if length > 0:\n",
    "                    #     merged = False\n",
    "                    #     for i in range(length-1, -1, -1):\n",
    "                    #         if buy_list[i].mPrice < buy_object.mPrice:\n",
    "                    #             buy_list.append(buy_object)\n",
    "                    #             buy_list.extend(tmp_list)\n",
    "                    #             merged = True\n",
    "                    #             break\n",
    "                    #         elif buy_list[i].mPrice == buy_object.mPrice:\n",
    "                    #             buy_list[i].mAmount += buy_object.mAmount\n",
    "                    #             buy_list.extend(tmp_list)\n",
    "                    #             merged = True\n",
    "                    #             break\n",
    "                    #         else:\n",
    "                    #             tmp_list.insert(0,buy_list[i])\n",
    "                    #             buy_list.pop(i)\n",
    "                    #     if not merged:\n",
    "                    #         if buy_object.mAmount > 0:\n",
    "                    #             buy_list.append(buy_object)\n",
    "                    #         buy_list.extend(tmp_list)\n",
    "                    # else:\n",
    "                    #     buy_list.append(buy_object)\n",
    "        \n",
    "        rs = 0\n",
    "        for o in buy_list:\n",
    "            rs = (rs + o.mAmount) % 1000000007\n",
    "        for o in sell_list:\n",
    "            rs = (rs + o.mAmount) % 1000000007\n",
    "        return rs\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heapify, heappush, heappop\n",
    "\n",
    "import functools as ft\n",
    "\n",
    "class Solution:\n",
    "    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:\n",
    "        modNum = 10**9 + 7\n",
    "        buyBacklog, sellBacklog = [], []\n",
    "        for eachBatchOrder in orders:\n",
    "            match eachBatchOrder[2]:\n",
    "                case 0:  # Buy\n",
    "                    while sellBacklog and sellBacklog[0][0] <= eachBatchOrder[0] and eachBatchOrder[1]:\n",
    "                        dealNum = min(sellBacklog[0][1], eachBatchOrder[1])\n",
    "                        sellBacklog[0][1] -= dealNum\n",
    "                        eachBatchOrder[1] -= dealNum\n",
    "                        if not sellBacklog[0][1]:\n",
    "                            heappop(sellBacklog)\n",
    "                    else:\n",
    "                        if eachBatchOrder[1]:\n",
    "                            eachBatchOrder[0] *= -1\n",
    "                            heappush(buyBacklog, eachBatchOrder)\n",
    "                case 1:  # Sell\n",
    "                    while buyBacklog and -buyBacklog[0][0] >= eachBatchOrder[0] and eachBatchOrder[1]:\n",
    "                        dealNum = min(buyBacklog[0][1], eachBatchOrder[1])\n",
    "                        buyBacklog[0][1] -= dealNum\n",
    "                        eachBatchOrder[1] -= dealNum\n",
    "                        if not buyBacklog[0][1]:\n",
    "                            heappop(buyBacklog)\n",
    "                    else:\n",
    "                        if eachBatchOrder[1]:\n",
    "                            heappush(sellBacklog, eachBatchOrder)\n",
    "        return (ft.reduce(lambda x,y: ((x%modNum) + (y[1]%modNum)) % modNum, buyBacklog, 0) % modNum +\\\n",
    "            ft.reduce(lambda x,y: ((x%modNum) + (y[1]%modNum)) % modNum, sellBacklog, 0) % modNum) % modNum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:\n",
    "        # 堆\n",
    "        buy = list()\n",
    "        sell = list()\n",
    "        for price,amount,t in orders:\n",
    "            if t == 0:  # buy\n",
    "                while amount > 0 and sell and sell[0][0] <= price:\n",
    "                    if sell[0][1] <= amount:\n",
    "                        amount -= sell[0][1]\n",
    "                        heapq.heappop(sell)\n",
    "                    else:\n",
    "                        sell[0][1] -= amount\n",
    "                        amount = 0\n",
    "                    #print(price,amount,'sell',sell)\n",
    "                if amount > 0:\n",
    "                    heapq.heappush(buy,[-price,amount])\n",
    "            else:   # sell\n",
    "                while amount > 0 and buy and -buy[0][0] >= price:\n",
    "                    if buy[0][1] <= amount:\n",
    "                        amount -= buy[0][1]\n",
    "                        heapq.heappop(buy)\n",
    "                    else:\n",
    "                        buy[0][1] -= amount\n",
    "                        amount = 0\n",
    "                if amount > 0:\n",
    "                    heapq.heappush(sell,[price,amount])\n",
    "            #print(buy,sell)\n",
    "        return (sum([x[1] for x in buy]) + sum([x[1] for x in sell])) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        buyOrders, sellOrders = [], []\n",
    "        for price, amount, type in orders:\n",
    "            if type == 0:\n",
    "                while amount and sellOrders and sellOrders[0][0] <= price:\n",
    "                    if sellOrders[0][1] > amount:\n",
    "                        sellOrders[0][1] -= amount\n",
    "                        amount = 0\n",
    "                        break\n",
    "                    amount -= heappop(sellOrders)[1]\n",
    "                if amount:\n",
    "                    heappush(buyOrders, [-price, amount])\n",
    "            else:\n",
    "                while amount and buyOrders and -buyOrders[0][0] >= price:\n",
    "                    if buyOrders[0][1] > amount:\n",
    "                        buyOrders[0][1] -= amount\n",
    "                        amount = 0\n",
    "                        break\n",
    "                    amount -= heappop(buyOrders)[1]\n",
    "                if amount:\n",
    "                    heappush(sellOrders, [price, amount])\n",
    "        return (sum(x for _, x in buyOrders) + sum(x for _, x in sellOrders)) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:\n",
    "\n",
    "        buybacklog = []\n",
    "        sellbacklog = []\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(orders)\n",
    "        for i in range(n):\n",
    "            if orders[i][2] == 0:\n",
    "                while orders[i][1] and sellbacklog and sellbacklog[0][0] <= orders[i][0]:\n",
    "                    if sellbacklog[0][1] > orders[i][1]:\n",
    "                        sellbacklog[0][1] -= orders[i][1]\n",
    "                        orders[i][1] = 0\n",
    "                        break\n",
    "                    orders[i][1] -= sellbacklog[0][1]\n",
    "                    heapq.heappop(sellbacklog)\n",
    "                if orders[i][1]:\n",
    "                    heapq.heappush(buybacklog, [-orders[i][0], orders[i][1]])\n",
    "\n",
    "            elif orders[i][2] == 1:\n",
    "                while orders[i][1] and buybacklog and -buybacklog[0][0] >= orders[i][0]:\n",
    "                    if buybacklog[0][1] > orders[i][1]:\n",
    "                        buybacklog[0][1] -= orders[i][1]\n",
    "                        orders[i][1] = 0\n",
    "                        break\n",
    "                    orders[i][1] -= buybacklog[0][1]\n",
    "                    heapq.heappop(buybacklog)\n",
    "                if orders[i][1]:\n",
    "                    heapq.heappush(sellbacklog, [orders[i][0], orders[i][1]])\n",
    "\n",
    "        return (sum(x for _, x in buybacklog) + sum(x for _, x in sellbacklog)) % MOD\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        buyOrders, sellOrders = [], []\n",
    "        for price, amount, type in orders:\n",
    "            if type == 0:\n",
    "                while amount and sellOrders and sellOrders[0][0] <= price:\n",
    "                    if sellOrders[0][1] > amount:\n",
    "                        sellOrders[0][1] -= amount\n",
    "                        amount = 0\n",
    "                        break\n",
    "                    amount -= heappop(sellOrders)[1]\n",
    "                if amount:\n",
    "                    heappush(buyOrders, [-price, amount])\n",
    "            else:\n",
    "                while amount and buyOrders and -buyOrders[0][0] >= price:\n",
    "                    if buyOrders[0][1] > amount:\n",
    "                        buyOrders[0][1] -= amount\n",
    "                        amount = 0\n",
    "                        break\n",
    "                    amount -= heappop(buyOrders)[1]\n",
    "                if amount:\n",
    "                    heappush(sellOrders, [price, amount])\n",
    "        return (sum(x for _, x in buyOrders) + sum(x for _, x in sellOrders)) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        buyOrders, sellOrders = [], []\n",
    "        for price, amount, type in orders:\n",
    "            if type == 0:\n",
    "                while amount and sellOrders and sellOrders[0][0] <= price:\n",
    "                    if sellOrders[0][1] > amount:\n",
    "                        sellOrders[0][1] -= amount\n",
    "                        amount = 0\n",
    "                        break\n",
    "                    amount -= heappop(sellOrders)[1]\n",
    "                if amount:\n",
    "                    heappush(buyOrders, [-price, amount])\n",
    "            else:\n",
    "                while amount and buyOrders and -buyOrders[0][0] >= price:\n",
    "                    if buyOrders[0][1] > amount:\n",
    "                        buyOrders[0][1] -= amount\n",
    "                        amount = 0\n",
    "                        break\n",
    "                    amount -= heappop(buyOrders)[1]\n",
    "                if amount:\n",
    "                    heappush(sellOrders, [price, amount])\n",
    "        return (sum(x for _, x in buyOrders) + sum(x for _, x in sellOrders)) % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from heapq import heappush, heappop\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, p, a):\n",
    "        self.p = p\n",
    "        self.a = a\n",
    "    \n",
    "    def __lt__(self, others):\n",
    "        return self.p <= others.p\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:\n",
    "        b = []\n",
    "        s = []\n",
    "        for p, a, o in orders:\n",
    "            if o == 0:\n",
    "                if not s:\n",
    "                    heappush(b, Node(-p, a))\n",
    "                    continue\n",
    "                while s:\n",
    "                    node = heappop(s)\n",
    "                    if node.p > p:\n",
    "                        heappush(s, node)\n",
    "                        heappush(b, Node(-p, a))\n",
    "                        break\n",
    "                    else:\n",
    "                        if node.a == a:\n",
    "                            break\n",
    "                        elif node.a > a:\n",
    "                            node.a -= a\n",
    "                            heappush(s, node)\n",
    "                            break\n",
    "                        else:\n",
    "                            a -= node.a\n",
    "                else:\n",
    "                    if a:\n",
    "                        heappush(b, Node(-p, a))\n",
    "            else:\n",
    "                if not b:\n",
    "                    heappush(s, Node(p, a))\n",
    "                    continue\n",
    "                while b:\n",
    "                    node = heappop(b)\n",
    "                    if -node.p < p:\n",
    "                        heappush(b, node)\n",
    "                        heappush(s, Node(p, a))\n",
    "                        break\n",
    "                    else:\n",
    "                        if node.a == a:\n",
    "                            break\n",
    "                        elif node.a > a:\n",
    "                            node.a -= a\n",
    "                            heappush(b, node)\n",
    "                            break\n",
    "                        else:\n",
    "                            a -= node.a \n",
    "                else:\n",
    "                    if a:\n",
    "                        heappush(s, Node(p, a))       \n",
    "        mod = 10**9 + 7\n",
    "        ans = 0\n",
    "        for node in s:\n",
    "            ans += node.a\n",
    "            ans %= mod\n",
    "        for node in b:\n",
    "            ans += node.a\n",
    "            ans %= mod\n",
    "        return ans\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        buyOrders, sellOrders = [], []\n",
    "        for price, amount, type in orders:#每次浏览一个订单\n",
    "\n",
    "            if type == 0:#这是一个买家\n",
    "                while amount and sellOrders and sellOrders[0][0] <= price:\n",
    "                    #每次循环结束之后结束一次订单匹配\n",
    "                    if sellOrders[0][1] > amount:\n",
    "                        sellOrders[0][1] -= amount\n",
    "                        amount = 0\n",
    "                        break\n",
    "                    amount -= heappop(sellOrders)[1]\n",
    "                    \n",
    "                if amount:\n",
    "                    heappush(buyOrders, [-price, amount])\n",
    "\n",
    "            else:\n",
    "                while amount and buyOrders and -buyOrders[0][0] >= price:\n",
    "                    if buyOrders[0][1] > amount:\n",
    "                        buyOrders[0][1] -= amount\n",
    "                        amount = 0\n",
    "                        break\n",
    "                    amount -= heappop(buyOrders)[1]\n",
    "                if amount:\n",
    "                    heappush(sellOrders, [price, amount])\n",
    "        return (sum(x for _, x in buyOrders) + sum(x for _, x in sellOrders)) % MOD\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        buyOrders, sellOrders = [], []\n",
    "        for price, amount, type in orders:\n",
    "            if type == 0:\n",
    "                while amount and sellOrders and sellOrders[0][0] <= price:\n",
    "                    if sellOrders[0][1] > amount:\n",
    "                        sellOrders[0][1] -= amount\n",
    "                        amount = 0\n",
    "                        break\n",
    "                    amount -= heappop(sellOrders)[1]\n",
    "                if amount:\n",
    "                    heappush(buyOrders, [-price, amount])\n",
    "            else:\n",
    "                while amount and buyOrders and -buyOrders[0][0] >= price:\n",
    "                    if buyOrders[0][1] > amount:\n",
    "                        buyOrders[0][1] -= amount\n",
    "                        amount = 0\n",
    "                        break\n",
    "                    amount -= heappop(buyOrders)[1]\n",
    "                if amount:\n",
    "                    heappush(sellOrders, [price, amount])\n",
    "        return (sum(x for _, x in buyOrders) + sum(x for _, x in sellOrders)) % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Number of Orders in the Backlog\n",
    "import heapq\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:\n",
    "        buy = []\n",
    "        sell = []\n",
    "\n",
    "        for o in orders:\n",
    "            # buy case\n",
    "            if o[2] == 0:\n",
    "                while len(sell) >0 and o[1]>0 and sell[0][0] <= o[0]:\n",
    "                    sellOrder = heapq.heappop(sell)\n",
    "                    if sellOrder[1] <= o[1]:\n",
    "                        o[1] = o[1] - sellOrder[1]\n",
    "                    else:\n",
    "                        sellOrder[1] = sellOrder[1] - o[1]\n",
    "                        heapq.heappush(sell,[sellOrder[0],sellOrder[1]])\n",
    "                        o[1] = 0\n",
    "                if o[1] > 0:\n",
    "                    heapq.heappush(buy, [-o[0],o[1]])\n",
    "            else:\n",
    "                while len(buy) > 0 and o[1] > 0 and -buy[0][0] >= o[0]:\n",
    "                    buyOrder = heapq.heappop(buy)\n",
    "                    if buyOrder[1] <= o[1]:\n",
    "                        o[1] = o[1] - buyOrder[1]\n",
    "                    else:\n",
    "                        buyOrder[1] = buyOrder[1] - o[1]\n",
    "                        heapq.heappush(buy, [buyOrder[0],buyOrder[1]])\n",
    "                        o[1] = 0\n",
    "                if o[1] > 0:\n",
    "                    heapq.heappush(sell,[o[0],o[1]])\n",
    "        ans = 0\n",
    "        for i in buy:\n",
    "            ans+=i[1]\n",
    "        for i in sell:\n",
    "            ans +=i[1]\n",
    "\n",
    "        return ans % (1000000000 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:\n",
    "        mod = 10**9+7\n",
    "        sell = [] # 最小堆 价格：数量\n",
    "        buy = [] # 最大堆\n",
    "        for p, a, o in orders:\n",
    "            # buy\n",
    "            if o == 0:\n",
    "                while a and sell and p >= sell[0][0]:\n",
    "                    if sell[0][1] > a:\n",
    "                        sell[0][1] -= a\n",
    "                        a = 0\n",
    "                        break\n",
    "                    a -= heappop(sell)[1]\n",
    "                if a:\n",
    "                    heappush(buy,[-p,a])\n",
    "            # sell\n",
    "            else:\n",
    "                while a and buy and p <= -buy[0][0]:\n",
    "                    if buy[0][1] > a:\n",
    "                        buy[0][1] -= a\n",
    "                        a = 0\n",
    "                        break\n",
    "                    a -= heappop(buy)[1]\n",
    "                if a:\n",
    "                    heappush(sell,[p,a])\n",
    "        return (sum(x for _,x in sell)+sum(x for _,x in buy))%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:\n",
    "        buy, sell = [], []\n",
    "        for p, a, t in orders:\n",
    "            if t == 0:\n",
    "                while a and sell and sell[0][0] <= p:\n",
    "                    x, y = heappop(sell)\n",
    "                    if a >= y:\n",
    "                        a -= y\n",
    "                    else:\n",
    "                        heappush(sell, (x, y-a))\n",
    "                        a = 0\n",
    "                if a:\n",
    "                    heappush(buy, (-p, a))\n",
    "            else:\n",
    "                while a and buy and -buy[0][0] >= p:\n",
    "                    x, y = heappop(buy)\n",
    "                    if a > y:\n",
    "                        a -= y\n",
    "                    else:\n",
    "                        heappush(buy, (x, y-a))\n",
    "                        a = 0\n",
    "                if a:\n",
    "                    heappush(sell, (p, a))\n",
    "        return sum(v[1] for v in buy + sell) % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:\n",
    "        buy, sell = [], []\n",
    "        for p, a, t in orders:\n",
    "            if t == 0:\n",
    "                while a and sell and sell[0][0] <= p:\n",
    "                    x, y = heappop(sell)\n",
    "                    if a >= y:\n",
    "                        a -= y\n",
    "                    else:\n",
    "                        heappush(sell, (x, y - a))\n",
    "                        a = 0\n",
    "                if a:\n",
    "                    heappush(buy, (-p, a))\n",
    "            else:\n",
    "                while a and buy and -buy[0][0] >= p:\n",
    "                    x, y = heappop(buy)\n",
    "                    if a >= y:\n",
    "                        a -= y\n",
    "                    else:\n",
    "                        heappush(buy, (x, y - a))\n",
    "                        a = 0\n",
    "                if a:\n",
    "                    heappush(sell, (p, a))\n",
    "        mod = 10**9 + 7\n",
    "        return sum(v[1] for v in buy + sell) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        buyOrders, sellOrders = [], []\n",
    "        for price, amount, type in orders:\n",
    "            if type == 0:\n",
    "                while amount and sellOrders and sellOrders[0][0] <= price:\n",
    "                    if sellOrders[0][1] > amount:\n",
    "                        sellOrders[0][1] -= amount\n",
    "                        amount = 0\n",
    "                        break\n",
    "                    amount -= heappop(sellOrders)[1]\n",
    "                if amount:\n",
    "                    heappush(buyOrders, [-price, amount])\n",
    "            else:\n",
    "                while amount and buyOrders and -buyOrders[0][0] >= price:\n",
    "                    if buyOrders[0][1] > amount:\n",
    "                        buyOrders[0][1] -= amount\n",
    "                        amount = 0\n",
    "                        break\n",
    "                    amount -= heappop(buyOrders)[1]\n",
    "                if amount:\n",
    "                    heappush(sellOrders, [price, amount])\n",
    "        return (sum(x for _, x in buyOrders) + sum(x for _, x in sellOrders)) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:\n",
    "        sell_heapq = []\n",
    "        buy_heapq = []\n",
    "        import heapq\n",
    "        heapq.heapify(sell_heapq)\n",
    "        heapq.heapify(buy_heapq)\n",
    "        for i in orders:\n",
    "            if i[2] == 1:\n",
    "                while buy_heapq:\n",
    "                    buy_order = heapq.heappop(buy_heapq)\n",
    "                    # print(buy_order)\n",
    "                    if -buy_order[0] >= i[0]:\n",
    "                        if buy_order[1] >= i[1]:\n",
    "                            buy_order[1] = buy_order[1]-i[1]\n",
    "                            i[1] = 0\n",
    "                            heapq.heappush(buy_heapq,buy_order)\n",
    "                            break\n",
    "                        else:\n",
    "                            i[1] = i[1]-buy_order[1] \n",
    "                    else:\n",
    "                        heapq.heappush(buy_heapq,buy_order)\n",
    "                        break\n",
    "                if i[1]>0:\n",
    "                    # print((sell_heapq,i))\n",
    "                    heapq.heappush(sell_heapq,i)\n",
    "            else:\n",
    "                while sell_heapq:\n",
    "                    sell_order = heapq.heappop(sell_heapq)\n",
    "                    if sell_order[0] <= i[0]:\n",
    "                        if sell_order[1] >= i[1]:\n",
    "                            sell_order[1] = sell_order[1]-i[1]\n",
    "                            i[1] = 0\n",
    "                            heapq.heappush(sell_heapq,sell_order)\n",
    "                            break\n",
    "                        else:\n",
    "                            i[1] = i[1]-sell_order[1] \n",
    "                    else:\n",
    "                        heapq.heappush(sell_heapq,sell_order)\n",
    "                        break\n",
    "                if i[1]>0:\n",
    "                    i[0] = -i[0]\n",
    "                    heapq.heappush(buy_heapq,i)\n",
    "            # print(buy_heapq)\n",
    "            # print(sell_heapq)\n",
    "        ret = 0\n",
    "        while buy_heapq:\n",
    "            buy_order = heapq.heappop(buy_heapq)\n",
    "            ret += buy_order[1]\n",
    "        while sell_heapq:\n",
    "            buy_order = heapq.heappop(sell_heapq)\n",
    "            ret += buy_order[1]\n",
    "        return ret %(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:\n",
    "        buy, sell = [], []\n",
    "        for p, a, t in orders:\n",
    "            if t == 0:\n",
    "                while a and sell and sell[0][0] <= p:\n",
    "                    x, y = heappop(sell)\n",
    "                    if a >= y:\n",
    "                        a -= y\n",
    "                    else:\n",
    "                        heappush(sell, (x, y - a))\n",
    "                        a = 0\n",
    "                if a != 0:\n",
    "                    heappush(buy, (-p, a))\n",
    "            else:\n",
    "                while a and buy and -buy[0][0] >= p:\n",
    "                    x, y = heappop(buy)\n",
    "                    if a >= y:\n",
    "                        a -= y\n",
    "                    else:\n",
    "                        heappush(buy, (x, y - a))\n",
    "                        a = 0\n",
    "                if a:\n",
    "                    heappush(sell, (p, a))\n",
    "        mod = 10**9 + 7\n",
    "        return sum(v[1] for v in buy + sell) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:\n",
    "        sell_heap = [] # 最小堆，存(价格, 数量)\n",
    "        buy_heap = [] # 最小堆，存(-价格, 数量)\n",
    "        res = 0\n",
    "        for price, amount, otype in orders:\n",
    "            if otype == 0: # 购买查sell_heap\n",
    "                diff = amount\n",
    "                while diff:\n",
    "                    if not sell_heap:\n",
    "                        heappush(buy_heap, [-price, diff])\n",
    "                        res += diff\n",
    "                        break\n",
    "                    elif sell_heap[0][0] <= price:\n",
    "                        if sell_heap[0][1] > diff:\n",
    "                            sell_heap[0][1] -= diff\n",
    "                            res -= diff\n",
    "                            break\n",
    "                        else:\n",
    "                            _, count = heappop(sell_heap)\n",
    "                            diff -= count\n",
    "                            res -= count\n",
    "                    else:\n",
    "                        heappush(buy_heap, [-price, diff])\n",
    "                        res += diff\n",
    "                        break\n",
    "            else: # 出售查buy_heap\n",
    "                diff = amount\n",
    "                while diff:\n",
    "                    if not buy_heap:\n",
    "                        heappush(sell_heap, [price, diff])\n",
    "                        res += diff\n",
    "                        break\n",
    "                    elif -buy_heap[0][0] >= price:\n",
    "                        if buy_heap[0][1] >diff:\n",
    "                            buy_heap[0][1] -= diff\n",
    "                            res -= diff\n",
    "                            break\n",
    "                        else:\n",
    "                            _, count = heappop(buy_heap)\n",
    "                            diff -= count\n",
    "                            res -= count\n",
    "                    else:\n",
    "                        heappush(sell_heap, [price, diff])\n",
    "                        res += diff\n",
    "                        break\n",
    "        return res%(pow(10, 9)+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:\n",
    "        res=0\n",
    "        md=1000000007\n",
    "        hp=[[],[]]\n",
    "        for i in orders:\n",
    "            v=i\n",
    "            tg=(v[2]+1)%2\n",
    "            mt=v[2]*2-1\n",
    "            while hp[tg] and hp[tg][0][0]<=v[0]*mt*(-1) and v[1]>0:\n",
    "                mn=min(v[1],hp[tg][0][1])\n",
    "                hp[tg][0][1]-=mn\n",
    "                if hp[tg][0][1]==0:\n",
    "                    heappop(hp[tg])\n",
    "                v[1]-=mn\n",
    "            if v[1]>0:\n",
    "                heappush(hp[v[2]],[mt*v[0],v[1]])\n",
    "        for i in hp:\n",
    "            while i:\n",
    "                res=(res+(i.pop())[1])%md\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:\n",
    "        buy_heap, sell_heap = [], []\n",
    "        for p,a,o in orders:\n",
    "            if o:\n",
    "                while a and buy_heap and -buy_heap[0][0] >= p:\n",
    "                    if a >= buy_heap[0][1]:\n",
    "                        a-=heapq.heappop(buy_heap)[1]\n",
    "                    else:\n",
    "                        buy_heap[0][1] -= a \n",
    "                        a = 0\n",
    "                if a :\n",
    "                    heapq.heappush(sell_heap, [p,a])\n",
    "            else:\n",
    "                while a and sell_heap and sell_heap[0][0] <= p:\n",
    "                    if a >= sell_heap[0][1]:\n",
    "                        a-=heapq.heappop(sell_heap)[1]\n",
    "                    else:\n",
    "                        sell_heap[0][1] -= a \n",
    "                        a = 0\n",
    "                if a :\n",
    "                    heapq.heappush(buy_heap, [-p,a])\n",
    "        return sum([a for _, a in sell_heap + buy_heap]) % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:\n",
    "        # sell\n",
    "        minHeap = []\n",
    "        # buy\n",
    "        maxHeap = []\n",
    "        for price, amount, orderType in orders:\n",
    "            if orderType == 0:\n",
    "                while minHeap and minHeap[0][0] <= price and amount > 0:\n",
    "                    p, a, o = heapq.heappop(minHeap)\n",
    "                    b = min(a, amount)\n",
    "                    a, amount = a - b, amount - b\n",
    "                    if a > 0:\n",
    "                        heapq.heappush(minHeap, [p, a, o])\n",
    "                if amount > 0:\n",
    "                    heapq.heappush(maxHeap, [-price, amount, orderType])\n",
    "            else:\n",
    "                while maxHeap and -maxHeap[0][0] >= price and amount > 0:\n",
    "                    p, a, o = heapq.heappop(maxHeap)\n",
    "                    p = -p\n",
    "                    b = min(a, amount)\n",
    "                    a, amount = a - b, amount - b\n",
    "                    if a > 0:\n",
    "                        heapq.heappush(maxHeap, [-p, a, o])\n",
    "                if amount > 0:\n",
    "                    heapq.heappush(minHeap, [price, amount, orderType])\n",
    "        result = sum(e[1] for e in minHeap)\n",
    "        result += sum(e[1] for e in maxHeap)\n",
    "        return result % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\r\n",
    "class Solution:\r\n",
    "    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:\r\n",
    "        heap_buy = []\r\n",
    "        heap_sell = []\r\n",
    "        for price, amount, orderType in orders:\r\n",
    "            if orderType == 0:\r\n",
    "                while amount and heap_sell and heap_sell[0][0]<=price:\r\n",
    "                    if amount>=heap_sell[0][1]:\r\n",
    "                        amount-=heap_sell[0][1]\r\n",
    "                        heapq.heappop(heap_sell)\r\n",
    "                    else:\r\n",
    "                        heap_sell[0][1]-=amount\r\n",
    "                        amount=0\r\n",
    "                if amount:\r\n",
    "                    heapq.heappush(heap_buy,[-price, amount])\r\n",
    "            else:\r\n",
    "                while amount and heap_buy and -heap_buy[0][0]>=price:\r\n",
    "                    if amount>=heap_buy[0][1]:\r\n",
    "                        amount-=heap_buy[0][1]\r\n",
    "                        heapq.heappop(heap_buy)\r\n",
    "                    else:\r\n",
    "                        heap_buy[0][1]-=amount\r\n",
    "                        amount=0\r\n",
    "                if amount:\r\n",
    "                    heapq.heappush(heap_sell,[price, amount])\r\n",
    "            \r\n",
    "        res = 0\r\n",
    "        for price, amount in heap_buy+heap_sell:\r\n",
    "            res = (res+amount)%(10**9+7)\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # * 优先队列模拟\n",
    "    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        buyOrders, sellOrders = [], []\n",
    "        for price, amount, type in orders:\n",
    "            if type == 0:\n",
    "                while amount and sellOrders and sellOrders[0][0] <= price:\n",
    "                    if sellOrders[0][1] > amount:\n",
    "                        sellOrders[0][1] -= amount\n",
    "                        amount = 0\n",
    "                        break\n",
    "\n",
    "                    amount -= heappop(sellOrders)[1]\n",
    "\n",
    "                if amount:\n",
    "                    heappush(buyOrders, [-price, amount])\n",
    "            else:\n",
    "                while amount and buyOrders and -buyOrders[0][0] >= price:\n",
    "                    if buyOrders[0][1] > amount:\n",
    "                        buyOrders[0][1] -= amount\n",
    "                        amount = 0\n",
    "                        break\n",
    "\n",
    "                    amount -= heappop(buyOrders)[1]\n",
    "\n",
    "                if amount:\n",
    "                    heappush(sellOrders, [price, amount])\n",
    "\n",
    "        return (sum(x for _, x in buyOrders) + sum(x for _, x in sellOrders)) % MOD\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:\n",
    "        buy=[]\n",
    "        sell=[]\n",
    "        for price,amount,c in orders:\n",
    "            #print(buy,sell,price,amount,c)\n",
    "            if c==1:#sell\n",
    "                while amount>0 and buy and -buy[0][0]>=price:\n",
    "                    p,a=heapq.heappop(buy)\n",
    "                    if a>amount:  \n",
    "                        heapq.heappush(buy,(p,a-amount))\n",
    "                        amount=0\n",
    "                    elif a<amount:\n",
    "                        amount-=a\n",
    "                    else:\n",
    "                        amount=0\n",
    "                if amount>0:\n",
    "                    heapq.heappush(sell,(price,amount))\n",
    "            if c==0:#buy\n",
    "                while amount>0 and sell and sell[0][0]<=price:\n",
    "                    p,a=heapq.heappop(sell)\n",
    "                    #print(p,a,amount,a-amount)\n",
    "                    if a>amount:                       \n",
    "                        heapq.heappush(sell,(p,a-amount))\n",
    "                        amount=0\n",
    "                    elif a<amount:\n",
    "                        amount-=a\n",
    "                    else:\n",
    "                        amount=0\n",
    "                if amount>0:\n",
    "                    heapq.heappush(buy,(-price,amount))\n",
    "        ret=0\n",
    "        mod=10**9+7\n",
    "        #print(buy,sell)\n",
    "        while buy:\n",
    "            p,c=buy.pop()\n",
    "            ret+=c\n",
    "            ret%=mod\n",
    "            #print(c,ret)\n",
    "        while sell:\n",
    "            p,c=sell.pop()\n",
    "            ret+=c\n",
    "            ret%=mod\n",
    "            #print(c,ret)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:\n",
    "        MOD = 10**9+7\n",
    "        sell_heap = []  # 最小堆\n",
    "        buy_heap = []   # 最大堆\n",
    "        for i in range(len(orders)):\n",
    "            cur_order = orders[i]\n",
    "            price, amount, otype = cur_order[0],cur_order[1],cur_order[2]\n",
    "            if cur_order[2]==0:\n",
    "                # buy\n",
    "                while sell_heap and amount>0 and sell_heap[0][0]<=price:\n",
    "                    tprice,tnum,tp = heapq.heappop(sell_heap)\n",
    "                    if tnum>=amount:\n",
    "                        tnum -= amount\n",
    "                        amount = 0\n",
    "                        if tnum>0:\n",
    "                            heapq.heappush(sell_heap, (tprice, tnum, tp))\n",
    "                    else:\n",
    "                        amount -= tnum\n",
    "                if amount>0:\n",
    "                    heapq.heappush(buy_heap, (-price, amount, otype))\n",
    "            else:\n",
    "                # sell\n",
    "                while buy_heap and amount>0 and -buy_heap[0][0]>=price:\n",
    "                    tprice,tnum,tp = heapq.heappop(buy_heap)\n",
    "                    if tnum>=amount:\n",
    "                        tnum -= amount\n",
    "                        amount = 0\n",
    "                        if tnum>0:\n",
    "                            heapq.heappush(buy_heap, (tprice, tnum, tp))\n",
    "                    else:\n",
    "                        amount -= tnum\n",
    "                if amount>0:\n",
    "                    heapq.heappush(sell_heap, (price, amount, otype))\n",
    "            \n",
    "            pass\n",
    "        res = 0\n",
    "        for e in buy_heap:\n",
    "            res += e[1]\n",
    "        for e in sell_heap:\n",
    "            res += e[1]\n",
    "        return res%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        buyOrders, sellOrders = [], []\n",
    "        for price, amount, typeb in orders:\n",
    "            if typeb == 0:\n",
    "                while amount and sellOrders and sellOrders[0][0] <= price:\n",
    "                    if sellOrders[0][1] > amount:\n",
    "                        sellOrders[0][1] -= amount\n",
    "                        amount = 0\n",
    "                        break\n",
    "                    amount -= heappop(sellOrders)[1]\n",
    "                if amount:\n",
    "                    heappush(buyOrders, [-price, amount])\n",
    "            else:\n",
    "                while amount and buyOrders and -buyOrders[0][0] >= price:\n",
    "                    if buyOrders[0][1] > amount:\n",
    "                        buyOrders[0][1] -= amount\n",
    "                        amount = 0\n",
    "                        break\n",
    "                    amount -= heappop(buyOrders)[1]\n",
    "                if amount:\n",
    "                    heappush(sellOrders, [price, amount])\n",
    "        return (sum(x for _, x in buyOrders) + sum(x for _, x in sellOrders)) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:\n",
    "        buy = Counter()\n",
    "        sell = Counter() \n",
    "        h1 = [float('-inf')]\n",
    "        h2 = [float('inf')]\n",
    "        buy[float('-inf')] = 1 \n",
    "        sell[float('inf')] = 1\n",
    "\n",
    "        for p, c, t in orders:\n",
    "            if t == 0:\n",
    "                while h2 and h2[0] <= p:\n",
    "                    x = h2[0] \n",
    "                    if sell[x] > c:\n",
    "                        sell[x]-=c\n",
    "                        c = 0\n",
    "                        break \n",
    "                    else: \n",
    "                        c -= sell[x]\n",
    "                        sell[x] = 0\n",
    "                        heapq.heappop(h2)\n",
    "                if c:\n",
    "                    buy[p] +=c \n",
    "                    heapq.heappush(h1, -p)\n",
    "            else:\n",
    "                while h1 and h1[0] <= -p:\n",
    "                    x = -h1[0]\n",
    "                    if buy[x] > c:\n",
    "                        buy[x] -= c\n",
    "                        c = 0 \n",
    "                        break \n",
    "                    else:\n",
    "                        c -= buy[x]\n",
    "                        buy[x] = 0\n",
    "                        heapq.heappop(h1)\n",
    "                if c:\n",
    "                    sell[p] += c \n",
    "                    heapq.heappush(h2, p)\n",
    "\n",
    "        ans = 0 \n",
    "        Mod = int(1e9+7)\n",
    "        for x, v in sell.items():\n",
    "            if x != float('inf'):\n",
    "                ans = (ans + v)%Mod \n",
    "        for x, v in buy.items():\n",
    "            if x != float('-inf'):\n",
    "                ans = (ans + v)%Mod \n",
    "        return ans\n",
    "\n",
    "\n",
    "                        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:\n",
    "        # sell\n",
    "        minHeap = []\n",
    "        # buy\n",
    "        maxHeap = []\n",
    "        for price, amount, orderType in orders:\n",
    "            if orderType == 0:\n",
    "                while minHeap and minHeap[0][0] <= price and amount > 0:\n",
    "                    if minHeap[0][1] <= amount:\n",
    "                        amount -= heapq.heappop(minHeap)[1]\n",
    "                    else:\n",
    "                        minHeap[0][1] -= amount\n",
    "                        amount = 0\n",
    "                if amount > 0:\n",
    "                    heapq.heappush(maxHeap, [-price, amount])\n",
    "            else:\n",
    "                while maxHeap and -maxHeap[0][0] >= price and amount > 0:\n",
    "                    if maxHeap[0][1] <= amount:\n",
    "                        amount -= heapq.heappop(maxHeap)[1]\n",
    "                    else:\n",
    "                        maxHeap[0][1] -= amount\n",
    "                        amount = 0\n",
    "                if amount > 0:\n",
    "                    heapq.heappush(minHeap, [price, amount])\n",
    "        result = sum(x for _, x in minHeap) + sum(x for _, x in maxHeap)\n",
    "        return result % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        buyOrders, sellOrders = [], []\n",
    "        for price, amount, type in orders:\n",
    "            if type == 0:\n",
    "                while amount and sellOrders and sellOrders[0][0] <= price:\n",
    "                    if sellOrders[0][1] > amount:\n",
    "                        sellOrders[0][1] -= amount\n",
    "                        amount = 0\n",
    "                        break\n",
    "                    amount -= heappop(sellOrders)[1]\n",
    "                if amount:\n",
    "                    heappush(buyOrders, [-price, amount])\n",
    "            else:\n",
    "                while amount and buyOrders and -buyOrders[0][0] >= price:\n",
    "                    if buyOrders[0][1] > amount:\n",
    "                        buyOrders[0][1] -= amount\n",
    "                        amount = 0\n",
    "                        break\n",
    "                    amount -= heappop(buyOrders)[1]\n",
    "                if amount:\n",
    "                    heappush(sellOrders, [price, amount])\n",
    "        return (sum(x for _, x in buyOrders) + sum(x for _, x in sellOrders)) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # * 优先队列模拟\n",
    "    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        buyOrders, sellOrders = [], []\n",
    "        for price, amount, type in orders:\n",
    "            if type == 0:\n",
    "                while amount and sellOrders and sellOrders[0][0] <= price:\n",
    "                    if sellOrders[0][1] > amount:\n",
    "                        sellOrders[0][1] -= amount\n",
    "                        amount = 0\n",
    "                        break\n",
    "\n",
    "                    amount -= heappop(sellOrders)[1]\n",
    "\n",
    "                if amount:\n",
    "                    heappush(buyOrders, [-price, amount])\n",
    "            else:\n",
    "                while amount and buyOrders and -buyOrders[0][0] >= price:\n",
    "                    if buyOrders[0][1] > amount:\n",
    "                        buyOrders[0][1] -= amount\n",
    "                        amount = 0\n",
    "                        break\n",
    "\n",
    "                    amount -= heappop(buyOrders)[1]\n",
    "\n",
    "                if amount:\n",
    "                    heappush(sellOrders, [price, amount])\n",
    "\n",
    "        return (sum(x for _, x in buyOrders) + sum(x for _, x in sellOrders)) % MOD\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq as hq\n",
    "class Solution:\n",
    "    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:\n",
    "        mod=10**9+7\n",
    "        buy=[]\n",
    "        sell=[]\n",
    "        r=0\n",
    "        for p,amount,t in orders:\n",
    "            amount=amount%mod\n",
    "            if t==0:\n",
    "                if len(sell)!=0:\n",
    "                    while p>=sell[0][0] and amount>0:\n",
    "                        sellp,sellmount=hq.heappop(sell)\n",
    "                        if amount>=sellmount:\n",
    "                            amount=amount-sellmount\n",
    "                        else:\n",
    "                            sellmount=sellmount-amount\n",
    "                            amount=0\n",
    "                            hq.heappush(sell,[sellp,sellmount]) \n",
    "                        if len(sell)==0:\n",
    "                            break\n",
    "                    #print(p,amount)    \n",
    "                    if amount>0:\n",
    "                        hq.heappush(buy,[-p,amount])\n",
    "                else:\n",
    "                    hq.heappush(buy,[-p,amount])\n",
    "            if t==1:\n",
    "                if len(buy)!=0:\n",
    "                    while p<=abs(buy[0][0]) and amount>0:\n",
    "                        buyp,buymount=hq.heappop(buy)\n",
    "                        buyp=-buyp\n",
    "                        if amount>=buymount:\n",
    "                            amount=amount-buymount\n",
    "                        else:\n",
    "                            buymount=buymount-amount\n",
    "                            amount=0\n",
    "                            hq.heappush(buy,[-buyp,buymount]) \n",
    "                        if len(buy)==0:\n",
    "                            break\n",
    "                    if amount>0:\n",
    "                        hq.heappush(sell,[p,amount])\n",
    "                else:\n",
    "                    hq.heappush(sell,[p,amount])\n",
    "            #print(r)\n",
    "            #r=r+1\n",
    "           # print(buy)\n",
    "            #print(sell)\n",
    "        ans=0\n",
    "      \n",
    "        while buy:\n",
    "            ans+=hq.heappop(buy)[1]\n",
    "        while sell:\n",
    "            ans+=hq.heappop(sell)[1]\n",
    "        return ans%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:\n",
    "        buy_heap, sell_heap = [], []\n",
    "        for p,a,o in orders:\n",
    "            if o:\n",
    "                while a and buy_heap and -buy_heap[0][0] >= p:\n",
    "                    if a < buy_heap[0][1]:\n",
    "                        buy_heap[0][1] -= a \n",
    "                        a = 0\n",
    "                        break\n",
    "                    a -= heapq.heappop(buy_heap)[1]\n",
    "                if a :\n",
    "                    heapq.heappush(sell_heap, [p,a])\n",
    "            else:\n",
    "                while a and sell_heap and sell_heap[0][0] <= p:\n",
    "                    if a < sell_heap[0][1]:\n",
    "                        sell_heap[0][1] -= a\n",
    "                        a = 0\n",
    "                        break \n",
    "                    a -= heapq.heappop(sell_heap)[1]\n",
    "                if a :\n",
    "                    heapq.heappush(buy_heap, [-p,a])\n",
    "        return sum([a for _, a in sell_heap + buy_heap]) % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:\n",
    "        buy, sell = [], []\n",
    "        for p, a, t in orders:\n",
    "            if t == 0: # 买\n",
    "                from_heap, to_heap, from_is_sell = sell, buy, True\n",
    "            else:\n",
    "                from_heap, to_heap, from_is_sell = buy, sell, False\n",
    "            while a and from_heap and (from_heap[0][0] <= p if from_is_sell else -from_heap[0][0] >= p):\n",
    "                cur = heapq.heappop(from_heap) # 调用heapq模块，建立小根堆\n",
    "                if cur[1] > a:\n",
    "                    heapq.heappush(from_heap, (cur[0], cur[1] - a))\n",
    "                    a = 0\n",
    "                else:\n",
    "                    a -= cur[1]\n",
    "            if a:\n",
    "                heapq.heappush(to_heap, (-p if from_is_sell else p, a))\n",
    "        ans, mod = 0, int(1e9)+7\n",
    "        for _, a in buy + sell:\n",
    "            ans += a\n",
    "        return ans % mod\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:\n",
    "        buy, sell = [], []\n",
    "        for p, a, t in orders:\n",
    "            if t == 0:\n",
    "                while a and sell and sell[0][0] <= p:\n",
    "                    x, y = heappop(sell)\n",
    "                    if a >= y:\n",
    "                        a -= y\n",
    "                    else:\n",
    "                        heappush(sell, (x, y - a))\n",
    "                        a = 0\n",
    "                if a:\n",
    "                    heappush(buy, (-p, a))\n",
    "            else:\n",
    "                while a and buy and -buy[0][0] >= p:\n",
    "                    x, y = heappop(buy)\n",
    "                    if a >= y:\n",
    "                        a -= y\n",
    "                    else:\n",
    "                        heappush(buy, (x, y - a))\n",
    "                        a = 0\n",
    "                if a:\n",
    "                    heappush(sell, (p, a))\n",
    "        mod = 10**9 + 7\n",
    "        return sum(v[1] for v in buy + sell) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:\n",
    "        '''\n",
    "        orders[i] = [pricei, amounti, orderTypei]\n",
    "        '''\n",
    "        buy_backlog = []\n",
    "        sell_backlog = []\n",
    "\n",
    "        for order in orders:\n",
    "            price, amount, ordertype = order\n",
    "            if ordertype == 0:\n",
    "                # this is a buy order\n",
    "                while sell_backlog and sell_backlog[0][0] <= price and amount > 0:\n",
    "                    sell_price, sell_amount = heapq.heappop(sell_backlog)\n",
    "                    if amount - sell_amount >= 0:\n",
    "                        amount -= sell_amount\n",
    "                    else:\n",
    "                        heapq.heappush(sell_backlog, (sell_price, sell_amount - amount))\n",
    "                        amount = 0\n",
    "                if amount > 0:\n",
    "                    heapq.heappush(buy_backlog, (-price, amount))\n",
    "            else:\n",
    "                # this is a sell order\n",
    "                while buy_backlog and -buy_backlog[0][0] >= price and amount > 0:\n",
    "                    buy_price, buy_amount = heapq.heappop(buy_backlog)\n",
    "                    buy_price = -buy_price\n",
    "                    if amount - buy_amount >= 0:\n",
    "                        amount -= buy_amount\n",
    "                    else:\n",
    "                        heapq.heappush(buy_backlog, (-buy_price, buy_amount - amount))\n",
    "                        amount = 0\n",
    "                if amount > 0:\n",
    "                    heapq.heappush(sell_backlog, (price, amount))\n",
    "                \n",
    "        constant = 10 ** 9 + 7\n",
    "        ret = 0\n",
    "        for order in buy_backlog + sell_backlog:\n",
    "            ret += order[1]\n",
    "            ret %= constant\n",
    "        return ret\n",
    "    \n",
    "\n",
    "\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def check(pq, price, order_type):\n",
    "    return price <= pq[0].price if order_type else price >= pq[0].price\n",
    "\n",
    "class Solution:\n",
    "    class Order:\n",
    "        def __init__(self, price, amount, order_type):\n",
    "            self.price = price\n",
    "            self.amount = amount\n",
    "            self.order_type = order_type\n",
    "        def __lt__(self, other):\n",
    "            if self.order_type: return self.price < other.price\n",
    "            return self.price > other.price\n",
    "        def __le__(self, other):\n",
    "            if self.order_type: return self.price <= other.price\n",
    "            return self.price >= other.price\n",
    "        def __gt__(self, other):\n",
    "            if self.order_type: return self.price > other.price\n",
    "            return self.price < other.price\n",
    "        def __ge__(self, other):\n",
    "            if self.order_type: return self.price >= other.price\n",
    "            return self.price <= other.price\n",
    "        def __eq__(self, other):\n",
    "            if self.order_type: return self.price == other.price\n",
    "            return self.price == other.price\n",
    "        def get_price(self):\n",
    "            return self.price\n",
    "        def get_amount(self):\n",
    "            return self.amount\n",
    "        def __sub__(self, other):\n",
    "            if isinstance(other, Solution.Order):\n",
    "                self.amount -= other.amount\n",
    "            self.amount -= other\n",
    "        def __repr__(self):\n",
    "            if self.order_type: return f\"Sell({self.price}, {self.amount})\"\n",
    "            return f\"Buy({self.price}, {self.amount})\"\n",
    "    \n",
    "    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:\n",
    "        pq1 = []\n",
    "        pq2 = []\n",
    "        pq = []\n",
    "        another = []\n",
    "        for order in orders:\n",
    "            price = order[0]\n",
    "            amount = order[1]\n",
    "            order_type = (order[2] == 1)\n",
    "            if order_type:\n",
    "                pq = pq1\n",
    "                another = pq2\n",
    "            else:\n",
    "                pq = pq2 \n",
    "                another = pq1\n",
    "            while pq and check(pq, price, order_type) and amount >= pq[0].amount:\n",
    "                amount -= heapq.heappop(pq).amount\n",
    "            if pq and check(pq, price, order_type):\n",
    "                pq[0].amount -= amount\n",
    "                amount = 0\n",
    "            if amount > 0:\n",
    "                heapq.heappush(another, Solution.Order(price, amount, order_type))\n",
    "\n",
    "        result = 0\n",
    "        while pq1:\n",
    "            result += heapq.heappop(pq1).amount\n",
    "        while pq2:\n",
    "            result += heapq.heappop(pq2).amount\n",
    "        return result % (1000000007)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:\n",
    "        buy, sell = [], []\n",
    "        for p, a, t in orders:\n",
    "            if not t:\n",
    "                while a and sell and sell[0][0] <= p:\n",
    "                    if sell[0][1] > a:\n",
    "                        sell[0][1] -= a\n",
    "                        a = 0\n",
    "                        break\n",
    "                    a -= heappop(sell)[1]\n",
    "                if a:\n",
    "                    heappush(buy, [-p, a])\n",
    "            else:\n",
    "                while a and buy and -buy[0][0] >= p:\n",
    "                    if buy[0][1] > a:\n",
    "                        buy[0][1] -= a\n",
    "                        a = 0\n",
    "                        break\n",
    "                    a -= heappop(buy)[1]\n",
    "                if a:\n",
    "                    heappush(sell, [p, a])\n",
    "        mod = 10**9 + 7\n",
    "        return sum(v[1] for v in buy + sell) % mod\n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
